
import java.util.Arrays;
import java.util.Stack;

/**
 * @ClassName IStack
 * @Description TODO
 * @Author ZJX
 * @Date 2024/9/18 14:15
 * @Version 1.0
 */
public class IStack {
    //    栈的底层是数组
    private int[] elem;
    private int usedSize;

    //默认容量
    final int DEFAULT_CAPACITY = 10;

    public IStack(){
        this.elem = new int[DEFAULT_CAPACITY];
    }

    public void push(int val){
        if (isFull()){
            elem = Arrays.copyOf(elem, elem.length * 2);
        }

        elem[usedSize] = val;
        usedSize++;
    }

    public int peek() {
//        获取栈顶元素
        if (isEmpty()) {
            System.out.println("栈空");
            return -1;
        }
        return elem[usedSize - 1];
    }


    public int pop(){
//        弹出元素
        if (isEmpty()){
            System.out.println("栈为空 无法获取元素!");
            throw new IllegalStateException("Stack is empty");
        }
        usedSize--;
        return elem[usedSize];
    }

    private boolean isFull() {
        return usedSize == elem.length;
    }

    public  boolean isEmpty(){
        return usedSize == 0;
    }

    /*
     * @param tokens:
      * @return int
     * @author: ZJX
     * @description: 逆波兰表达式
     * @date: 2024/9/18 15:12
     */
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for(String s : tokens){
            if (!isOperation(s)){
                stack.push(Integer.parseInt(s));
            } else {
                int num2 = stack.pop();
                int num1 = stack.pop();
                switch (s){
                    case "+" :
                        stack.push(num1 + num2);
                        break;
                    case "-" :
                        stack.push(num1 - num2);
                        break;
                    case "*":
                        stack.push(num1 * num2);
                        break;
                    case "/":
                        stack.push(num1 / num2);
                        break;
                }
            }
        }
        return stack.pop();
    }

    private boolean isOperation(String s){
        return s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/");
    }

    /*
     * @param s:
      * @return boolean
     * @author: ZJX
     * @description: 括号匹配
     * @date: 2024/9/18 17:19
     */
    public boolean isValid(String s) {
//        遇到的第一个右括号跟最后一个左括号进行匹配 (利用栈的性质)
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (ch == '(' || ch == '{'|| ch == '[') {
                stack.push(ch);
            } else {
//                说明是右括号
                if (stack.isEmpty()){
                    return false;
                }
                Character top = stack.pop();
                if ((ch == ')' && top != '(') || (ch == '}' && top != '{') || (ch == ']' && top != '[')) {
                    return false;
                }
            }
        }
        return true;
    }

    /*
     * @param pushV:
    	 * @param popV:
      * @return boolean
     * @author: ZJX
     * @description: 栈的压入 弹出序列
     * @date: 2024/9/18 18:15
     */
    public boolean IsPopOrder(int[] pushV, int[] popV) {
        Stack<Integer> stack = new Stack<>();
        int popIndex = 0;
        for (int x : pushV){
            stack.push(x);
            while (!stack.isEmpty() && popV[popIndex] == stack.peek()){
                stack.pop();
                popIndex++;
            }
        }
        return stack.isEmpty();
    }
}
